10192 - Vacation/p10192.cpp

   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11 #include <iostream>
  12 #include <string>
  13
  14 #define MAX(a,b) ((a>b)?(a):(b))
  15
  16 using namespace std;
  17
  18 int dp[1001][1001];
  19
  20 int lcs(const string &s, const string &t){
  21   int m = s.size(), n = t.size();
  22   if (m == 0 || n == 0) return 0;
  23   for (int i=0; i<=m; ++i)
  24     dp[i][0] = 0;
  25   for (int j=1; j<=n; ++j)
  26     dp[0][j] = 0;
  27   for (int i=0; i<m; ++i)
  28     for (int j=0; j<n; ++j)
  29       if (s[i] == t[j])
  30         dp[i+1][j+1] = dp[i][j]+1;
  31       else
  32         dp[i+1][j+1] = MAX(dp[i+1][j], dp[i][j+1]);
  33   return dp[m][n];
  34
  35
  36
  37 }
  38
  39 int main(){
  40   string s, t;
  41   getline(cin, s);
  42   getline(cin, t);
  43   int caso = 1;
  44   while (!cin.eof()){
  45     cout << "Case #"<< caso <<": you can visit at most " << lcs(s, t) << " cities." << endl;
  46     ++caso;
  47     getline(cin, s);
  48     if (s == "#") break;
  49     getline(cin, t);
  50   }
  51   return 0;
  52 }